package y_2025.m03.d05;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;

public class MaxGap {

// 返回数组中最小元素的下标（针对double类型）
    public static int mini(int n, double[] x) {
        double temp = x[0];
        int k = 0;
        for (int i = 1; i < n; i++) {
            if (x[i] < temp) {
                temp = x[i];
                k = i;
            }
        }
        return k;
    }

    // 返回数组中最大元素的下标（针对double类型）
    public static int maxi(int n, double[] x) {
        double temp = x[0];
        int k = 0;
        for (int i = 1; i < n; i++) {
            if (x[i] > temp) {
                temp = x[i];
                k = i;
            }
        }
        return k;
    }

    // 计算最大间隙
    public static double maxgap(int n, double[] x) {
        double minx = x[mini(n, x)];
        double maxx = x[maxi(n, x)];
        // 创建n-1个桶，每个桶有一个最小值和最大值
        int[] count = new int[n - 1];
        double[] low = new double[n - 1];
        double[] high = new double[n - 1];

        // 初始化这n-1个桶，数组最大值赋给每个桶的小值
        // 数组最小值赋给每个桶的大值
        for (int i = 0; i < n - 1; i++) {
            count[i] = 0;
            low[i] = maxx;
            high[i] = minx;
        }

        // 将数组中的n个元素分配n-1个桶中，并记录每个桶中的小值和大值
        for (int i = 0; i < n; i++) {
            // bucket是指每个元素应分到哪个桶的ID（ID=[0,1,...,n-2]）
            // bucket = (x[i] - minx) / 平均距离
            //        = (x[i] - minx) / ((maxx - minx) / (n - 1))
            //        = (n - 1) * (x[i] - minx) / (maxx - minx)
            // int起着向下取整的作用
            int bucket = (int) ((n - 1) * (x[i] - minx) / (maxx - minx));
            // 当x[i] = maxx时，bucket向下取整会取到n-1
            // 为了避免越界，强行将数组最大元素放在最后一个桶中
            if (bucket == (n - 1)) {
                bucket = n - 2;
            }
            count[bucket]++;
            if (x[i] < low[bucket]) {
                low[bucket] = x[i];
            }
            if (x[i] > high[bucket]) {
                high[bucket] = x[i];
            }
        }

        double temp = 0;
        double left = high[0];
        for (int i = 1; i < n - 1; i++) {
            if (count[i] > 0) {
                double thisgap = low[i] - left;
                if (thisgap > temp) {
                    temp = thisgap;
                }
                left = high[i];
            }
        }
        return temp;
    }

    public static void main(String[] args) {
        String infileName = "input.txt";
        String outfileName = "output.txt";
        int n;
        double[] a = new double[100];
        double result;

        // 读取文件
        try (Scanner infile = new Scanner(new File(infileName))) {
            n = infile.nextInt();  // 给参数n赋值
            // 给数组a赋值
            for (int i = 0; i < n; i++) {
                a[i] = infile.nextDouble();
            }
        } catch (FileNotFoundException e) {
            System.err.println("File not found: " + infileName);
            return;
        }

        // 计算
        result = maxgap(n, a);

        // 保存结果
        try (PrintWriter outfile = new PrintWriter(new File(outfileName))) {
            outfile.println(result);
        } catch (FileNotFoundException e) {
            System.err.println("File not found: " + outfileName);
        }
    }
}